package 栈和队列;

import java.util.Stack;

public class 迷宫问题 {
    int x = 0; //单元所在行
    int y = 0; //单元所在列
    boolean visited = false;//是否访问
    char c; //是墙（"1"）,可通路”0“,终点(*)

    public 迷宫问题(int x, int y, char c, boolean visited) {
        this.x = x;
        this.y = y;
        this.visited = visited;
        this.c = c;
    }

    public static void mazeExit(int[][] maze, int sx, int sy, int ex, int ey) {
        迷宫问题[][] cells = createMaze(maze); //创建化迷宫
        printMaze(cells); //打印迷宫
        Stack s = new Stack(); //构造堆栈
        迷宫问题 startCell = cells[sx][sy]; //起点
        迷宫问题 endCell = cells[ex][ey]; //终点
        s.push(startCell); //起点入栈
        startCell.visited = true; //标记起点已被访问
        while (!s.isEmpty()) {
            迷宫问题 current = (迷宫问题) s.peek();
            if (current == endCell) { //路径找到
                while (!s.isEmpty()) {
                    迷宫问题 cell = (迷宫问题) s.pop();//沿路返回将路径上的单元设为*
                    cell.c = '*';
                    //堆栈中与 cell 相邻的单元才是路径的组成部分，除此之外，
                    //堆栈中还有记录下来但是未继续向下探索的单元，
//这些单元直接出栈
                    while (!s.isEmpty() && !isAdjoinCell((迷宫问题) s.peek(), cell)) s.pop();
                }
                System.out.println("找到从起点到终点的路径。");
                printMaze(cells);
                return;
            } else { //如果当前位置不是终点
                int x = current.x;
                int y = current.y;
                int count = 0;
                if (isValidWayCell(cells[x + 1][y])) { //向下
                    s.push(cells[x + 1][y]);
                    cells[x + 1][y].visited = true;
                    count++;
                }
                if (isValidWayCell(cells[x][y + 1])) { //向右
                    s.push(cells[x][y + 1]);
                    cells[x][y + 1].visited = true;
                    count++;
                }
                if (isValidWayCell(cells[x - 1][y])) { //向上
                    s.push(cells[x - 1][y]);
                    cells[x - 1][y].visited = true;
                    count++;
                }
                if (isValidWayCell(cells[x][y - 1])) { //向左
                    s.push(cells[x][y - 1]);
                    cells[x][y - 1].visited = true;
                    count++;
                }
                if (count == 0) s.pop();//如果是死点，出栈
            }//end of if
        }//end of while
        System.out.println("没有从起点到终点的路径。");
    }


    private static 迷宫问题[][] createMaze(int[][] maze) {
        迷宫问题[][] cells = new 迷宫问题[maze.length][maze[0].length];
        for (int x = 0; x < maze.length; x++) {
            for (int y = 0; y < maze[0].length; y++) {
                char c = (char) (48 + maze[x][y]);
                cells[x][y] = new 迷宫问题(x, y, c, false);
            }
        }

        return cells;
    }

    private static boolean isValidWayCell(迷宫问题 cell) {
        return cell.c == '0' && !cell.visited;
    }

    private static boolean isAdjoinCell(迷宫问题 cell, 迷宫问题 cell2) {
        if (cell.x == cell2.x && Math.abs(cell.y - cell2.y) < 2) return true;
        if (cell.y == cell2.y && Math.abs(cell.x - cell2.x) < 2) return true;
        return false;
    }

    private static void printMaze(迷宫问题[][] cells) {

        for (int i = 0; i < cells.length; i++) {
            for (int j = 0; j < cells[0].length; j++) {
                if (j < cells[0].length - 1) {
                    System.out.print(cells[i][j].c + " ");
                } else {
                    System.out.println(cells[i][j].c);
                }

            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] nums = {{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 0, 0, 1, 1, 1, 0, 0, 1, 1},
                {1, 0, 0, 1, 1, 0, 0, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 0, 1, 0, 1},
                {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
                {1, 0, 0, 1, 1, 1, 0, 0, 0, 1},
                {1, 0, 0, 0, 0, 1, 0, 1, 0, 1},
                {1, 0, 1, 1, 0, 0, 0, 1, 0, 1},
                {1, 1, 0, 0, 0, 0, 1, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};

        mazeExit(nums, 8, 8, 1, 7);


    }

}


